#include <vector>
#include <ctime>
#include <random>
#include <iostream>
using std::vector;
using std::cout;
int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left;
    for (int j = left; j < right; ++j) {
        if (nums[j] > pivot) {
            std::swap(nums[i], nums[j]);
            ++i;
        }
    }
    std::swap(nums[i], nums[right]);
    return i;
}

int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) {
        return nums[left];
    }
    
    int pivotIndex = left + std::rand() % (right - left + 1);
    std::swap(nums[pivotIndex], nums[right]);
    pivotIndex = partition(nums, left, right);
    
    if (k == pivotIndex) {
        return nums[k];
    } else if (k < pivotIndex) {
        return quickSelect(nums, left, pivotIndex - 1, k);
    } else {
        return quickSelect(nums, pivotIndex + 1, right, k);
    }
}

int findKthLargestQuickSelect(std::vector<int>& nums, int k) {
    std::srand(std::time(0));
    return quickSelect(nums, 0, nums.size() - 1, k - 1);
}

int main() {
    vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;
    cout << "The nums is ";
    for(auto num:nums){
        cout << " " << num;
    }
    cout << "\n";
    cout << "The " << k << "th largest element is " << findKthLargestQuickSelect(nums, k) << "\n";
    return 0;
}
